7、偏序集

偏序集

定义：关系

$R$ 为 $X$ 上关系，若 $R \subset X \times X$ . 若 $(x, y) \in R$ ，记作 $x R y$ 。

定义：偏序集

偏序集为对子 $(X, R)$ ， $X$ 为有限集且 $R$ 为 $X$ 上偏序关系，满足：

反身性： $x R x$ 。
反对称性： $x R y$ 且 $y R x$ ，则 $x = y$ 。
传递性： $x R y$ 且 $y R z$ ，则 $x R z$ 。

偏序集例子

$(2^{[n]}, \subset)$ 。
$([n], ∣)$ 。

我们一般用 $⪯$ 表示偏序关系。若 $x ⪯ y$ 但 $x \neq y$ ，称 $x ≺ y$ ，此时称 $x$ 是 $y$ 的一个前驱（predecessor）。

定义：直接前驱（immediate predecessor）

若 $x ≺ y$ ，且不存在 $t$ 使 $x ≺ t ≺ y$ ，则称 $x$ 为 $y$ 的一个直接前驱，记作 $x ⊲ y$ 。

定理：前驱等价于直接前驱序列

$x ≺ y$ 等价于存在若干 $z_{1}, \dots, z_{k}$ ，使

x ⊲ z_{1} ⊲ \dots ⊲ z_{k} ⊲ y .

注：我们仅考虑有限集，因为这是组合学。

证明： 只证必要性。令 $M = {t \in X : x ≺ t ≺ y}$ ，对 $| M |$ 归纳。

若 $| M | = 0$ ，则 $x ⊲ y$ ，证毕。

若命题对 $| M | < n$ 成立，假设 $x ≺ y$ 且 $| M | = n$ ，对任意 $t \in M$ ，考虑 $x, t$ 的 $M_{1}$ 和 $t, y$ 的 $M_{2}$ 。由传递性可知 $M_{1} ⊊ M$ ， $M_{2} ⊊ M$ ，故 $| M_{1} |, | M_{2} | \leq n - 1$ ，于是

x ⊲ z_{1} ⊲ \dots ⊲ z_{t} ⊲ t ⊲ z_{1}^{'} ⊲ \dots ⊲ z_{s}^{'} ⊲ y .

Hasse 图

定义：Hasse图

$(X, ⪯)$ 的 Hasse 图定义为

$X$ 的每个元素被绘制为图中的结点；
若 $x ⊲ y$ ，则 $x, y$ 间有一个线；
若 $x ⊲ y$ ，则 $x$ 绘制在 $y$ 下方的平面内。

例如，如下是 $(2^{[3]}, \subset)$ 的 Hasse 图：

\begin{document}
\begin{tikzpicture}[scale=3]
\node[above] at (0,3) {$\{1,2,3\}$};
\node[left] at (-1,2) {$\{1,2\}$};
\node[left] at (0,2) {$\{2,3\}$};
\node[right] at (1,2) {$\{3,1\}$};
\node[left] at (-1,1) {$\{1\}$};
\node[left] at (0,1) {$\{2\}$};
\node[right] at (1,1) {$\{3\}$};

\node[below] at (0,0) {$\emptyset$};
\draw (0,3) -- (-1,2) -- (-1,1) -- (0,0) -- (1,1) -- (1,2) -- (0,3) -- (0,2) -- (1,1) -- (1,2) -- (-1,1) -- (-1,2) -- (0,1) -- (0,0);
\draw (0,1) -- (0,2);
\end{tikzpicture}
\end{document}

上面的定理等价于： $x ≺ y$ 当且仅当我们能在 Hasse 图中找到一条自 $x$ 到 $y$ 、严格从下到上的路径。

偏序集嵌入

定义：偏序集间嵌入

设 $(X_{1}, ⪯_{1})$ 、 $(X_{2}, ⪯_{2})$ 为二偏序集，称映射 $f : X_{1} \to X_{2}$ 为嵌入，若

$f$ 为单射，且
$f (x) ⪯_{2} f (y)$ 当且仅当 $x ⪯_{1} y$ 。

一个最重要的例子是

定理：偏序集的集合表示

对任一偏序集 $(X, ⪯)$ ，存在其到 $(2^{X}, \subset)$ 的一个嵌入。

证明： 考虑 $f : X \to 2^{X}$ ， $f (x) = {y \in X : y ⪯ x} .$

$f$ 为单射：若 $f (x) = f (y)$ ，由 $f (x) \subset f (y)$ 得 $x ⪯ y$ ，同理 $y ⪯ x$ ，故 $x = y$ 。

$f$ 保持偏序：正过去显然。现设 $f (x) \subset f (y)$ ，即对任意 $t ⪯ x$ 都有 $t ⪯ y$ ，取 $t = x$ 即证。

链与反链

定义

设 $P$ 为偏序集。

对任意 $x \neq y \in P$ ，若 $x ≺ y$ 或 $y ≺ x$ ，则称 $x, y$ 可比（comparable），否则不可比（incomparable）。
称 $A \subset P$ 为反链，若任意两个元素都不可比。记 $α (P)$ 为最大反链大小。
称 $B \subset X$ 为链，若任两个元素都可比。记 $ω (P)$ 为最大链大小。

在 Hasse 图中， $ω (P)$ 为各自上而下路径中最长一条的顶点数，故也称为 $P$ 的高（height）；称 $α (P)$ 为宽（width）。

定义：极小元、极大元

称 $x$ 极小，若其无前驱；极大元无后继。

注：全体极小元及极大元分别构成反链。

定理：反链与链长乘积估计

$α (P) \cdot ω (P) \geq | P |$ 。

证明： 证法是借助“刨根问底”式构造，或者拆汉堡，whatever。我们递规地定义一个偏序集列 $P_{i} = (X_{i}, ⪯_{i})$ 及集合列 $M_{i} \subset P_{i}$ ，使得 $M_{i}$ 为 $P_{i}$ 的极小元集，且 $X_{i} = X ∖ ⋃_{j = 1}^{i - 1} M_{j}$ .

首先，令 $P_{1} = P = (X, ⪯)$ ， $X_{1} = X$ 且 $M_{0} = \emptyset$ 。假设 $P_{i} = (X_{i}, ⪯)$ 、 $M_{i - 1}$ 对任意 $1 \leq i \leq k$ 定义，这里 $k$ 足够大。令 $M_{i} = {P_{i} 极小元}$ ，并令 $X_{i + 1} = X ∖ ⋃_{j = 1}^{n} M_{j}$ ，。令 $P_{i + 1}$ 为 $P$ 限制在 $X_{i + 1}$ 上的偏序集。我们不断这么做，直到 $X_{l + 1} = \emptyset$ 。则我们有

| M_{i} | \leq α (P_{i}) \leq α (P) .

由 $X = ⋃_{i = 1}^{l} M_{i}$ ，故 $| X | = \sum_{i = 1}^{l} | M_{i} | \leq α (P) \cdot l \leq α (P) \cdot ω (P)$ ，证毕。

事实上，我们可以证明更强的事实：若 $x \in M_{i}, i \geq 2$ ,则存在 $y \in M_{i - 1}$ 使得 $y ⊲ x$ 。

推论

若 $| P | = r s + 1$ ，则要么存在 $s + 1$ 大小的链，要么存在 $r + 1$ 大小的反链。

来自病症的订单

——好吧，是“来自无序的有序”（The Order From Disorder）

定义：有序子列

略。

定理（Erdos-Szekeres）

对任意长为 $m n + 1$ 的序列，其中必有长为 $m + 1$ 的单增子列或 $n + 1$ 的单减子列。

证明： 将这些序列视作偏序集 $P = (X, ⪯)$ ： $a_{i} ⪯ a_{j}$ 当且仅当 $i \leq j$ 与 $a_{i} \leq a_{j}$ 同时成立。由反链与链长乘积估计，要么有长为 $m + 1$ 的链（此时为单增子列），要么有长为 $n + 1$ 的反链（此时为单减子列）。

抽屉原理（The Pigeonhole Principle）

定理（抽屉原理）

$| ⨆_{i = 1}^{n} X_{i} | \geq 1 + \sum_{i = 1}^{n} (| X_{i} | - 1) ⟹ max | X_{i} | \geq n .$

例：度相等问题

例（0721）

任一图中有两个度相等的顶点。

证明： 否则，设 $G$ 中每个度都只出现一次，则必须 $d = 0, 1, \dots, | V | - 1$ 都充当一次度，但 $0$ 和 $| V | - 1$ 显然不能同时出现。

例：染色数（chromatic number）

定义：顶点染色

称图 $G = (V, E)$ 的一个顶点染色为映射 $f : V \to C$ ， $C$ 为颜色集。称一个顶点染色是适当的，若相邻两点不同色。
称染色数 $χ (G)$ 为 $G$ 的适当染色的颜色集可能的最小大小。

定理：染色数的估计

设 $G$ 有 $n$ 个点，则 $α (G) χ (G) \geq n$ 。

证明： 给定一个适当染色 $G$ ，颜色集大小为 $χ (G)$ 。将 $V$ 划分为 $χ (G)$ 个部分使得每个部分有相同颜色。注意到每个部分均为独立集，故存在一个独立集（一个部分），其大小至少为 $\frac{n}{χ (G)}$ ，故 $α (G) \geq \frac{n (G)}{χ (G)}$ 。

例：无因子子集（Subset without divisors）

定理：过半子集必有倍数关系

若 $S \subset [2 n]$ ， $| S | \geq n + 1$ ，则 $S$ 中必有两个数 $(i, j)$ 使 $i ∣ j$ 。反过来，最大使 $S$ 中无倍数关系的子集数为 $n$ 。

注：下面的证明说明，事实上可要求比值为 2 的幂次倍。

证明： 首先，显然 ${n + 1, \dots, 2 n}$ 无倍数关系。

其次，对任一奇数 $2 k - 1, k \in [n]$ ，令 $S_{2 k - 1} = {2^{i} \cdot (2 k - 1) \in S : i \geq 0}$ 。显然 $S = ⋃_{k = 1}^{n} S_{2 k - 1}$ 。由 $| S | \geq n + 1$ ，抽屉原理给出其中必有一个集合中至少有两个数，这两个数的比值为 2 的幂次倍。

例：有理逼近

定理：有理逼近的强化

给定 $n \in Z^{+}$ ，则对任意 $x \in R^{+}$ ，都存在 $p, q$ 使得

$q \leq n$ ，且
$| x - \frac{p}{q} | < \frac{1}{n q}$ 。

证明： 令 ${x} = x - ⌊ x ⌋$ 。考虑 ${i x} \in [0, 1)$ ， $i = 1, 2, \dots, n + 1$ 。

将 $[0, 1)$ 分为 $n$ 段： $[0, 1 / n), [1 / n, 2 / n], \dots, [(n - 1) / n, 1)$ 。由抽屉原理，必存在 ${i x}, {j x}$ 位于同一个区间。故

| (j - i) x - (⌊ j x ⌋ - ⌊ i x ⌋) | < \frac{1}{n} .

取 $q = j - i$ ， $p = ⌊ j x ⌋ - ⌊ i x ⌋$ ，即证。

Erdos-Szekeres 定理第二证

Erdos-Szekeres定理第二证： 考虑任意序列 ${a_{0}, a_{1}, \dots, a_{m n}}$ 。对任意 $i \in {0, 1, \dots, m n}$ ，令 $f_{i}$ 为从 $a_{i}$ 开始的最大递增子列长。设若 $f_{i} \in {1, 2, \dots, m}$ 对任意 $i \in {0, 1, \dots, m n}$ 成立，由抽屉原理知存在 $s \in {1, 2, \dots, m}$ 使得至少有 $n + 1$ 个下标 $i \in {0, 1, \dots, m n}$ 使 $f_{i} = s$ 。令这些元素为 $i_{1} < i_{2} < \dots < i_{n + 1}$ 。

我们声称 $a_{i_{1}} \geq a_{i_{2}} \geq \dots \geq a_{i_{n + 1}}$ 。事实上，若存在 $a_{i_{j}} < a_{i_{j + 1}}$ ，则我们可以将 $a_{i_{j + 1}}$ 处的最长递增链延长——将 $a_{i_{j}}$ 加入。这与 $a_{i_{j}}$ 处最长链长度为 $s$ 矛盾。

Mantel 定理

定理（Mantel）

任一无 $K_{3}$ 图至多有 $\frac{| V |^{2}}{4}$ 条边。

我们只证 $n := | V |$ 为偶的情况。

证明： 令 $n = 2 l$ 。对 $l$ 归纳。

$l = 1$ 显然。设命题对任意 $2 k < 2 l$ 个顶点时成立，则对顶点为 $2 k$ 的情形，含 $k^{2} + 1$ 条边的图有一个 $K_{3}$ 。现在令 $n = 2 l$ 且 $| E (G) | \geq l^{2} + 1$ 。任取一边 $x y$ ，并令 $H = G [V (G) ∖ {x, y}]$ 。若 $E (H) \geq (l - 1)^{2} + 1$ ，由归纳假设知 $H$ 有一个 $K_{3}$ ，矛盾。因此 $| E (H) | \leq (l - 1)^{2}$ ，这说明 ${x, y}$ 与 $H$ 之间的边数多于 $2 l - 1$ 。但 $| H | = 2 l - 2$ ，由抽屉原理知 $x, y$ 在 $H$ 中有一个公共顶点 $p$ ，但 $p x y$ 构成一个 $K_{3}$ ，矛盾！

推广

若 $G$ 无 $K_{k + 1}$ ，则 $| E (G) | \leq (1 - \frac{1}{k}) \frac{n^{2}}{2}$ 。

证明： $n = 1, 2, 3, \dots, k$ 时是显然的。下设命题对任意 $n < m$ 成立，则对 $n = m$ ，设若存在一个图 $G$ 无 $K_{k + 1}$ 且 $| E (G) | \geq (1 - \frac{1}{k}) \frac{n^{2}}{2} + 1$ ，则

分解到链与反链

偏序集的分解是将其划分为两两不交的链或反链。给定一个偏序集 $P$ ，目标是将其分解为尽可能少的链（或反链）。指导思想很简单：若一个偏序集有一个大小为 $r$ 的链（反链），则其将不可分解为比 $r$ 少的反链（链），原因是：在两种划分中，同一链（反链）中的两个点必在不同的反链（链）中。

练习（Mirsky）

假设 $P$ 中最大链大小为 $r$ ，则 $P$ 可被分解为 $r$ 个反链。

证明： 对任意 $x \in P$ ，定义 $x$ 的高度为以 $x$ 为最大元素的极大链的长度，记作 $ht x$ 。作分类：

A_{i} := {x \in P : ht x = i},

我们证明每个 $A_{i}$ 都是反链。否则，若存在某个 $x, y \in A_{i}$ 使得 $x < y$ ，由它们的高都是 $i$ ，存在一个长为 $i$ 的链 $C$ ，其以 $x$ 为最大元素；但 $C \cup {y}$ 是更长的一条链，因此 $ht y \geq i + 1$ ，矛盾！从而各 $A_{i}$ 为反链。

另一方面，由于最长的一条链大小为 $r$ ，则任一元素的高度至多为 $r$ 。此外，注意到对任意元素 $x \in P$ ，都存在至少一条链以 $x$ 为最大元素（至少可以是它自己一人成军），因此 $ht x \geq 1$ ，这说明由以上集给出的反链可以覆盖整个图。

最后，注意到一个链中的每个顶点必须在不同反链中，故上面给出的每个反链都非空。因此整个图恰可分为 $A_{1}, \dots, A_{r}$ 这些反链，证毕。

定理（Dilworth）

假设 $P$ 中最大的反链大小为 $r$ ，则 $P$ 可被分为 $r$ 个链。

证明： 对 $| P |$ 归纳。设 $a$ 为 $P$ 的一个极大元， $r$ 为 $P^{'} ∖ {a}$ 中最大反链的大小。则 $P^{'}$ 是 $r$ 个不交链 $C_{1}, \dots, C_{r}$ 之并。我们需要说明 $P$ 要么包含一个 $r + 1$ 元反链，或其为 $r$ 个不交链之并。现在， $P^{'}$ 中每个 $r$ 元反链的每个元素来自某个 $C_{i}$ 。设 $a_{i}$ 为 $C_{i}$ 中最大元素，含于 $P$ 的某些反链中。易知 $A = {a_{1}, \dots, a_{r}}$ 为 $P^{'}$ 中的反链。若 $A \cup {a}$ 是 $P$ 中反链，则证毕；否则，必有 $a ≻ a_{i}$ 对某个 $i$ ，因此 $K = {a} \cup {x \in C_{i} : x ⪯ a_{i}}$ 为 $P$ 中的一个链，且 $P ∖ K$ 中无 $r$ 元反链（因为 $a_{i}$ 是 $C_{i}$ 中参与此反链的极大元），同时 $P ∖ K$ 是 $r - 1$ 个链之并：因为整个链 $C_{i}$ 都被删掉了，无法构造出一个 $r$ 元反链。证毕。

练习

说明 Dilworth 分解定理蕴含 Hall 定理。

提示：构造一个偏序集 $X = S_{1} \cup \dots \cup S_{m}$ 及符号 $y_{1}, \dots, y_{m}$ ：若 $x \in S_{i}$ 则 $x < y_{i}$ ，且无其它可比性。

证明： 构造集合 $P = ⋃ S_{i} \cup {y_{1}, \dots, y_{m}}$ ，并定义提示所示的偏序。注意 $X$ 本身是一个反链。另一方面，若一个反链包含某些 ${y_{i}}_{i \in I} : I \subset [m]$ ，则该反链最大为

C_{I} = {y_{i} : i \in I} \cup (X ∖ ⋃_{i \in I} S_{i}) .

因此 $| C_{I} | \leq | I | + | X | - | ⋃_{i \in I} S_{i} |$ . 其它的反链均包含在 $X$ 或某个 $C_{I}$ 中。

下面来由此导出 Hall 定理。

若 Hall 条件恒成立，即对任意 $I \subset [m]$ 都有 $| I | \leq | ⋃_{i \in I} S_{i} |$ ，则 $| C_{I} | \leq | X |$ ，故最大反链长为 $| X |$ 。由 Dilworth 定理， $P$ 由 $| X |$ 个链所覆盖。但注意每个链要么形如 $S_{i} ∋ x < y_{i}$ ，要么是单元素链，设链覆盖中长为 2 的链有 $m^{'}$ 条，则长为 1 的链有 $| X | - m^{'}$ 条。则总元素数满足

m + | X | = | P | = 2 m^{'} + (| X | - m^{'}) ⟹ m^{'} = m .

故长为 2 的链恰为 $m$ 个。由于链覆盖不交，这些链对应的 $X$ 中元素即为一个SDR。

反之，若存在 $I$ 使 Hall 条件不成立，则最大反链不是 $X$ ，而是某个 $C_{I}$ 。对这个 $C_{I}$ 来说，同上知长为 1 的链有 $| C_{I} | - m^{'}$ 条，此时 $m^{'} = m + | X | - | C_{I} | < m$ ，故无法选出SDR。